package nbranch.tree.perorder;

import java.util.LinkedList;
import java.util.List;

/**
 * @Date 2020/03/15
 * @author 王光浩
 * @Thinking 使用迭代的方式完成。
 * @Analysis 时间复杂度O（n），空间复杂度O（2n）
 */
public class MyMethodTwo {
	public List<Integer> preorder(Node root) {
		if(root==null)return new LinkedList<Integer>();
		List<Integer> res=new LinkedList<Integer>();
		List<Node> node;
		LinkedList<List<Node>> stack=new LinkedList<>();
		stack.add(root.children);
		//进行迭代
		while(!stack.isEmpty()) {
			if(stack.peek()==null || stack.peek().isEmpty()) {
				stack.removeFirst();
				continue;
			}
			node=stack.peek();
			Node tem=node.remove(0);
			res.add(tem.val);
			stack.add(tem.children);
		}
		return res;
	}
}
